#include <stdio.h>
#include<string.h>
#include<stdlib.h>
#define max 50
int Allocation[max][max];
int Available[max];
int resources[max];
int Max[max][max];
int Need[max][max];
int resourcesSize;//资源总数
int processSize;//进程总数
bool isSecurity;//系统是否安全
bool checkSecurity();

void initialize()
{

    printf("请输入资源总数\n");
    scanf("%d",&resourcesSize);
    printf("输入各个资源的数量：\n");
    for(int i = 0;i<resourcesSize;i++)
    {
        printf("资源%d=",i);
        scanf("%d",&resources[i]);
    }
    printf("输入进程数量\n");
    scanf("%d",&processSize);
    printf("输入每个进程对资源的最大需求\n");
    for(int i = 0;i<processSize;i++)
    {
        for(int j = 0;j<resourcesSize;j++)
        {
            printf("进程%d对资源%d的最大需求=",i,j);
            scanf("%d",&Max[i][j]);
        }
    }
    printf("对每个进程的资源已分配情况：\n");
    for(int i = 0;i<processSize;i++)
    {
        for(int j = 0;j<resourcesSize;j++)
        {
            printf("已对进程%d分配资源%d的数量=",i,j);
            scanf("%d",&Allocation[i][j]);
        }
    }
    for(int i = 0;i<processSize;i++)
    {
        for(int j = 0;j<resourcesSize;j++)
        {
            Need[i][j] = Max[i][j] - Allocation[i][j];
        }
    }
    for(int j = 0;j<resourcesSize;j++)
    {

        for(int i = 0;i<processSize;i++)
        {
            resources[j] -= Allocation[i][j]; //分配完之后剩下的资源总数
        }
        Available[j] = resources[j];//可用资源数
    }
    checkSecurity();

}
bool checkSecurity()
{
    bool security[processSize];//security[i]表示进程i是否安全
    int securityQueue[processSize];//表示安全队列，将进程的id号加进去
    memset(security,false,processSize); //初始化为不安全的。
    int lastNoSecurity = processSize; //初始化上次不安全进程数为processSize
    int temp[max]; //避免检测时对Available数组进行修改
    for(int i = 0;i<resourcesSize;i++)
    {
        temp[i] = Available[i];
    }
    int k = 0;//添加安全进程到securityQueue中。计数的作用
    while(true)
    {
        int currentNoSecurity = 0;//每次检测都currentNoSecurity都从0开始计数，表示当前不安全的进程数
        int count;
        for(int i = 0;i<processSize;i++)
        {
            count = 0;
            if(security[i]==true) continue; //跳过安全的进程
            for(int j = 0;j<resourcesSize;j++)
            {
                if(Need[i][j]<=temp[j]) //资源数满足进程i对它的需求
                        count++;
                else
                    break;
            }
            if(count==resourcesSize)//所有可利用的资源全部满足进程i+1的需求,将此进程加入安全队列中
            {
                security[i] = true; //进程i是安全的
                //将进程i+1已分配的资源偿还
                printf("进程%d是安全的哦,资源可利用更新为：\n",i);
                for(int j = 0 ;j<resourcesSize;j++)
                {
                    temp[j]+=Allocation[i][j];
                    printf("%d ",temp[j]);
                }
                printf("\n");
                securityQueue[k++] = i;
            }
            //当不满足时，暂时说明此进程是不安全的，当前不安全进程数+1
            else
            {
                currentNoSecurity++;
                printf("进程%d现在还不安全\n",i);
            }
        }
        //检测一遍后，下面判断检测的结果
        if(currentNoSecurity==0) //检测完毕，所有进程都已加入安全队列中。系统可以进行资源分配了。
        {
            printf("当前系统是安全的，可以对进程进行资源分配，安全队列如下：\n");
            for(int i = 0;i< k;i++)
            {
                printf("%d ",securityQueue[i]);
            }
            printf("\n");
            return true;
        }
        //当下检测不是安全队列的进程数如果跟上次一样，就说明扫一遍后找不出符合安全性的进程了。
        if(currentNoSecurity==lastNoSecurity)
        {
            //不安全
            printf("当前系统是不安全的，不能进行资源的分配！");
            return false;
        }
        //至少有一个加入了安全队列中了，所以再扫一遍进程队列，再检测一遍。
        else{
            lastNoSecurity = currentNoSecurity;
        }

    }
    return false;
}
bool answerQuest()
{
    int Request[resourcesSize];
    printf("输入哪个进程的资源请求？\n");
    int process;
    scanf("%d",&process);
    for(int j = 0;j<resourcesSize;j++)
    {
        printf("输入进程%d对资源%d的请求=",process,j);
        scanf("%d",&Request[j]);
    }

    //有多少我就请求多少，这貌似合理，系统也是安全的。但是这是不对的！不能多于最大请求
    for(int j = 0;j<resourcesSize;j++)
    {
        if(Request[j] + Allocation[process][j] > Max[process][j]){
            printf("进程%d对资源%d的请求不合理，超出所宣布的最大值！",process,j);
            return false;
        }
    }
    //没有大于最大请求，但是当前系统可能还没有这么资源分配他们
    for(int j = 0;j<resourcesSize;j++)
    {
            if(Request[j] > Available[j])
            {
                printf("系统还没有足够的资源%d响应进程%d的请求",j,process);
            }
    }
    //尝试分配
    printf("尝试分配资源\n");
    for(int j = 0;j<resourcesSize;j++)
    {
        Allocation[process][j]+=Request[j];
        Need[process][j]-=Request[j];
    }
    for(int j = 0;j<resourcesSize;j++)
    {
        Available[j]-=Request[j];
    }
    if(!checkSecurity()){//如果系统不处于安全状态。则本次分配作废，恢复原来的资源分配状态
        printf("分配作废，恢复原来的状态\n");
            for(int j = 0;j<resourcesSize;j++)
            {

                Allocation[process][j] -= Request[j];
                Need[process][j] += Request[j];
            }
            for(int j = 0;j<resourcesSize;j++)
                {
                        Available[j] += Request[j];
                }
            return false;
    }
    return true;

}
void look()
{
    printf("最大资源需求：\n");
    for(int i = 0;i<processSize;i++)
    {
        for(int j = 0;j<resourcesSize;j++)
        {
            printf("%d\t",Max[i][j]);
        }
        printf("\n");
    }
    printf("已分配资源：\n");
    for(int i = 0;i<processSize;i++)
    {
        for(int j = 0;j<resourcesSize;j++)
        {
            printf("%d\t",Allocation[i][j]);
        }
        printf("\n");
    }
    printf("Need需求：\n");
    for(int i = 0;i<processSize;i++)
    {
        for(int j = 0;j<resourcesSize;j++)
        {
            printf("%d\t",Need[i][j]);
        }
        printf("\n");
    }
    printf("现有资源：\n");
    for(int j = 0;j<resourcesSize;j++)
    {
        printf("%d\t",Available[j]);
    }
    printf("\n");

}
void menu()
{
    printf("\n\n\t1.继续对进程进行资源的分配？\n");
    printf("\t2.查看资源情况\n");
    printf("\t3.exit\n");
}
int main()
{
    printf("\n\n\t\t银行家算法,欢迎使用!!!\t\t\n\n");
    printf("created by jiangzhengtao\n");
    printf("time:2018.6.28 17:43\n");
    printf("place：yifu building 431\n");
    printf("\n\t1.请输入系统的初始状态\n");
    initialize();
    int choose;
    while(1)
    {
        menu();
        scanf("%d",&choose);
        switch(choose)
        {
            case 1:
                if(answerQuest())
                    printf("请求成功！");
                else
                    printf("请求失败！");
                    break;
            case 2:look();break;
            case 3:
                printf("再见！");
                exit(0);
        }
    }
    return 0;
}



// #include <condition_variable>
// #include <iostream>
// #include <mutex>
// #include <string>
// #include <thread>
// #include <functional>
// #include <atomic>
// using namespace std;

// // 死锁测试
// std::mutex tx1, tx2;
// std::atomic<bool> StopFlags(false);
// std::condition_variable cv;
// void A()
// {
//     while (!StopFlags.load())
//     {
//         std::cout << "thread A is runing... sleep(3)" << std::endl;
//         std::unique_lock<std::mutex> _lck1(tx2, std::defer_lock);
//         std::unique_lock<std::mutex> _lck2(tx1, std::defer_lock);
//         std::lock(_lck1,_lck2);
//     }
// }

// void B()
// {
//     while (!StopFlags.load())
//     {
//         std::cout << "thread B is runing... sleep(3)" << std::endl;
//         std::unique_lock<std::mutex> _lck1(tx2, std::defer_lock);
//         std::unique_lock<std::mutex> _lck2(tx1, std::defer_lock);
//         std::lock(_lck1,_lck2);
//     }
// }

// int main()
// {
//     std::thread t1, t2;

//     std::cout << "准备启动线程了" << std::endl;
//     std::this_thread::sleep_for(std::chrono::seconds(3));

//     // 启动线程
//     if (!StopFlags.load())
//     {
//         std::cout << "Start thread..." << std::endl;
//         t1 = std::thread(A);
//         t2 = std::thread(B);
//     }

//     std::this_thread::sleep_for(std::chrono::seconds(3));

//     StopFlags = true;

//     if (StopFlags.load())
//     {
//         if (t1.joinable())
//         {
//             t1.join();
//         }
//         if (t2.joinable())
//         {

//             t2.join();
//         }
//     }
//     return 0;
// }

// // // 定义一个原子整数
// // // std::atomic<int> atomicCounter(0);
// // std::atomic<int> atomicCounter{0};

// // // 线程函数，对原子整数进行递增操作
// // void incrementCounter(int id, int iterations) {
// //     for (int i = 0; i < iterations; ++i) {
// //         // 原子递增操作
// //         ++atomicCounter;
// //         // 为了模拟一些工作负载，让线程稍微休眠一下
// //         std::this_thread::sleep_for(std::chrono::milliseconds(1));
// //     }
// //     std::cout << "Thread " << id << " finished its work." << std::endl;
// // }

// // int main() {
// //     // 定义线程数量和每个线程要执行的递增次数
// //     const int numThreads = 10;
// //     const int iterationsPerThread = 1000;

// //     // 创建一个线程向量来存储线程对象
// //     std::vector<std::thread> threads;

// //     // 创建并启动线程
// //     for (int i = 0; i < numThreads; ++i) {
// //         threads.emplace_back(incrementCounter, i, iterationsPerThread);
// //     }

// //     // 等待所有线程完成
// //     for (auto& thread : threads) {
// //         thread.join();
// //     }

// //     // 输出最终的原子整数值
// //     std::cout << "Final counter value: " << atomicCounter.load() << std::endl;

// //     return 0;
// // }
// // // 定义两个共享资源（整数变量）和两个互斥锁
// // int shared_resource1 = 0;
// // int shared_resource2 = 0;
// // std::mutex mtx1, mtx2;
// // // ⼀个函数，同时访问两个共享资源
// // void access_shared_resources()
// // {
// //     // std::unique_lock<std::mutex> lock1(mtx1, std::defer_lock);
// //     // std::unique_lock<std::mutex> lock2(mtx2, std::defer_lock);
// //     // // // 使⽤ std::lock 同时锁定两个互斥锁
// //     // std::lock(lock1, lock2);
// //     // 现在两个互斥锁都已锁定，可以安全地访问共享资源
// //     int cnt = 10000;
// //     while (cnt)
// //     {
// //         ++shared_resource1;
// //         ++shared_resource2;
// //         cnt--;
// //     }
// //     // 这会导致它们各⾃的互斥量被⾃动解锁
// // }
// // void simulate_concurrent_access()
// // {
// //     std::vector<std::thread> threads;
// //     // 创建多个线程来模拟并发访问
// //     for (int i = 0; i < 10; ++i)
// //     {
// //         threads.emplace_back(access_shared_resources);
// //     }
// //     for (auto &thread : threads)
// //     {
// //         thread.join();
// //     }
// //     std::cout << "Shared Resource 1: " << shared_resource1 << std::endl;
// //     std::cout << "Shared Resource 2: " << shared_resource2 << std::endl;
// // }
// // int main()
// // {
// //     simulate_concurrent_access();
// //     return 0;
// // }
// // void printFirst() { printf("first"); }
// // void printSecond() { printf("second"); }
// // void printThird() { printf("third"); }

// // class Foo {
// //     condition_variable cv;
// //     mutex mtx;
// //      int k = 0;
// // public:
// //     void first(function<void()> printFirst) {
// //         printFirst();
// //         k = 1;
// //         cv.notify_all();    // 通知其他所有在等待唤醒队列中的线程
// //     }
// //     void second(function<void()> printSecond) {
// //         unique_lock<mutex> lock(mtx);   // lock mtx
// //         cv.wait(lock, [this](){ return k == 1; });  // unlock mtx，并阻塞等待唤醒通知，需要满足 k == 1 才能继续运行
// //         printSecond();
// //         k = 2;
// //         cv.notify_one();    // 随机通知一个（unspecified）在等待唤醒队列中的线程
// //     }

// //     void third(function<void()> printThird) {
// //         unique_lock<mutex> lock(mtx);   // lock mtx
// //         cv.wait(lock, [this](){ return k == 2; });  // unlock mtx，并阻塞等待唤醒通知，需要满足 k == 2 才能继续运行
// //         printThird();
// //     }
// // };

// // int main()
// // {
// //     Foo f;
// //     std::thread t1(&Foo::first,&f,printFirst);
// //     std::thread t2(&Foo::second,&f,printThird);
// //     std::thread t3(&Foo::third,&f,printSecond);

// //     t1.join();
// //     t2.join();
// //     t3.join();

// //     return 0;
// // }

// // std::mutex m;
// // std::condition_variable cv;
// // std::string data;
// // bool ready = false;
// // bool processed = false;

// // void worker_thread()
// // {
// //     // 等待直至 main() 发送数据
// //     std::unique_lock lk(m);
// //     cv.wait(lk, []{ return ready; });

// //     // lk.lock(); //只要不报错就说明，wai完之后不会自动加锁
// //     //结论：会自动加锁
// //     // 等待后，我们占有锁
// //     std::cout << "工作线程正在处理数据\n";
// //     data += "（处理后）";

// //     // 发送数据回 main()
// //     processed = true;
// //     std::cout << "工作线程指示数据已经处理完成\n";

// //     // 通知前完成手动解锁，以避免等待线程才被唤醒就阻塞（细节见 notify_one）
// //     cv.notify_one();
// // }

// // int main()
// // {
// //     std::thread worker(worker_thread);

// //     data = "数据样例";
// //     // 发送数据到 worker 线程
// //     {
// //         std::lock_guard lk(m);
// //         ready = true;
// //         std::cout << "main() 指示数据已准备好进行处理\n";
// //     }
// //     cv.notify_one();

// //     // 等候 worker
// //     {
// //         std::unique_lock lk(m);
// //         cv.wait(lk, []{ return processed; });
// //     }
// //     std::cout << "返回 main()，data = " << data << '\n';

// //     worker.join();
// // }

// // #include <iostream>
// // #include <filesystem>
// // #include <fstream>
// // #include <sstream>
// // #include <memory>
// // #include <functional>
// // #include "Mutex.hpp"
// // #include "Cond.hpp"

// // using namespace std;
// // using namespace MyCond;
// // using namespace MpthreayMutex;
// // // template<class T>
// // // class A
// // // {
// // // public:
// // //     T data;
// // //     static A aa;
// // //     A() = delete;
// // //     A(const A& AA) = delete;
// // //     A& operaotr=(const A& aa) = delete;
// // //     static A* Instance()
// // //     {
// // //         return &aa;
// // //     }
// // // };

// // // int main()
// // // {
// // //     // A a = new A;
// // //     A<int>::Instance()->data = 20;
// // //     std::cout << A<int>::Instance()->data <<std::endl;

// // //     //查看目录是否存在
// // //     // if (std::filesystem::exists("./tt"))
// // //     // {
// // //     //     std::cout << "hello world" << std::endl;
// // //     // }
// // //     // else
// // //     // {
// // //     //     try
// // //     //     {
// // //     //         std::filesystem::create_directories("./tt");
// // //     //     }
// // //     //     catch(std::filesystem::filesystem_error & e)
// // //     //     {
// // //     //         std::cout << e.what() << std::endl;
// // //     //     }
// // //     // }

// // //     // std::ofstream out("./log.txt",std::ios::app); //一追加的方式打开，如果没有文件就创建
// // //     // if (out.is_open())
// // //     // {
// // //     //     //out.write()
// // //     //     out << "hello world " << std::endl;
// // //     // }
// // //     // out.close();

// // //     //字符串流，把任意 << 右边的值变为字符串

// // //     // std::stringstream ss;
// // //     // ss << "你好" << "牛逼" << 6666 << "123123" << 3.5 << "就这?" << std::endl;
// // //     // std::cout << ss.str() << std::endl;

// // //     return 0;
// // // }

// // void printFirst() { printf("first\n"); }
// // void printSecond() { printf("second\n"); }
// // void printThird() { printf("third\n"); }
// // int cnt = 1;
// // class Foo
// // {
// // public:
// //     Foo()
// //     {
// //     }
// //     void first(function<void()> printFirst)
// //     {
// //         // printFirst() outputs "first". Do not change or remove this line.
// //         while (true)
// //         {
// //             {
// //                 LockGround lock(_mtx);
// //                 if (cnt == 1)
// //                 {
// //                     printFirst();
// //                     cnt++;
// //                     _cond.Notify();
// //                     break;
// //                 }
// //                 else
// //                     _cond.wait(_mtx);
// //             }
// //         }
// //     }
// //     void second(function<void()> printSecond)
// //     {
// //         while (true)
// //         {
// //             {
// //                 LockGround lock(_mtx);
// //                 if (cnt == 2)
// //                 {

// //                     printSecond();
// //                     cnt++;
// //                     _cond.Notify();
// //                     break;
// //                 }
// //                 else
// //                     _cond.wait(_mtx);
// //             }
// //         }
// //         // printSecond() outputs "second". Do not change or remove this line.
// //     }
// //     void third(function<void()> printThird)
// //     {
// //         while (true)
// //         {
// //             {
// //                 LockGround lock(_mtx);
// //                 if (cnt == 3)
// //                 {
// //                     printThird();
// //                     cnt++;
// //                     _cond.Notify();
// //                     break;
// //                 }
// //                 else
// //                     _cond.wait(_mtx);
// //             }
// //         }
// //         // printThird() outputs "third". Do not change or remove this line.
// //     }

// // private:
// //     Mutex _mtx;
// //     Cond _cond;
// // };

// // void *run(void *args)
// // {
// //     auto callable = static_cast<std::function<void()> *>(args);
// //     (*callable)();
// //     delete callable; // 记得释放分配的内存
// //     return nullptr;
// // }
// // int main()
// // {
// //     Foo f;
// //     pthread_t tid1, tid2, tid3;
// //     auto f1 = [&f]()
// //     { f.first(printFirst); };
// //     auto f2 = [&f]()
// //     { f.second(printSecond); };
// //     auto f3 = [&f]()
// //     { f.third(printThird); };
// //     // function<void(function<void()>)> f10 = std::bind(&Foo::first,&f,std::placeholders::_1);
// //     // f10(printFirst);

// //     std::function<void()> *funcPtr1 = new std::function<void()>(f1);
// //     std::function<void()> *funcPtr2 = new std::function<void()>(f2);
// //     std::function<void()> *funcPtr3 = new std::function<void()>(f3);
// //     pthread_create(&tid1, nullptr, run, funcPtr1);
// //     pthread_create(&tid2, nullptr, run, funcPtr2);
// //     pthread_create(&tid3, nullptr, run, funcPtr3);
// //     pthread_join(tid1, nullptr);
// //     pthread_join(tid2, nullptr);
// //     pthread_join(tid3, nullptr);
// //     return 0;
// // }